package features.advance.leetcode.array.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 15. 三数之和
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 示例 2：
 *
 * 输入：nums = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：nums = [0]
 * 输出：[]
 *
 *
 * 提示：
 *
 * 0 <= nums.length <= 3000
 * -105 <= nums[i] <= 105
 *
 * @author LIN
 * @date 2021-04-27
 */
public class Solution15 {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                if(nums[second] > target){
                    System.out.println(ans);
                    continue;
                }
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] nums = {-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0};
        Solution15 solution15 = new Solution15() {

            @Override
            public List<List<Integer>> threeSum(int[] nums) {

                List<List<Integer>> list = new ArrayList<>();
                if (nums.length < 3){
                    return list;
                }
                Arrays.sort(nums);
                List<Integer> tempList;
                if(nums.length == 3 && (nums[0] + nums[1] + nums[2]) == 0){
                    tempList = new ArrayList<Integer>();
                    tempList.add(nums[0]);
                    tempList.add(nums[1]);
                    tempList.add(nums[2]);
                    list.add(tempList);
                    return list;
                }
                for (int i = 0; i < nums.length - 3; i++) {
                    if(nums[i] > 0){
                        return list;
                    }
                    if( i - 1 >= 0 && nums[i] == nums[i - 1]){
                        continue;
                    }
                    int tempNum = nums[i];
                    int left = i + 1;
                    int right = nums.length - 1;

                    // 82ms     11.88%
                    // 42.4MB   57.21%
                    // 封装对象提前声明，会大大提高效率和占用内存
            /*while(left < right ){
                tempList = new ArrayList<Integer>();
                tempList.add(tempNum);
                if((tempNum + nums[left] + nums[right]) > 0) {
                    right--;
                } else if ((tempNum + nums[left] + nums[right]) < 0) {
                    left++;
                } else if ((tempNum + nums[left] + nums[right]) == 0) {

                    tempList.add(nums[left]);
                    tempList.add(nums[right]);
                    list.add(tempList);
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right  && nums[right] == nums[right + 1]) right--;

                }
            }*/

                    // 19ms     99.78%
                    // 42.4MB   64.98%
                    while(left < right ){
                        if((tempNum + nums[left] + nums[right]) > 0) {
                            right--;
                            //while(left < right && nums[right] == nums[--right]);
                        } else if ((tempNum + nums[left] + nums[right]) < 0) {
                            //while(left < right && nums[left] == nums[++left]);
                            left++;
                        } else if ((tempNum + nums[left] + nums[right]) == 0) {
                            tempList = new ArrayList<Integer>();
                            tempList.add(tempNum);
                            tempList.add(nums[left]);
                            tempList.add(nums[right]);
                            list.add(tempList);
                            left++;
                            right--;
                            while (left < right && nums[left] == nums[left - 1]) left++;
                            while (left < right  && nums[right] == nums[right + 1]) right--;

                        }
                    }
                }
                return list;
            }
        };

        List<List<Integer>> lists = new Solution15(){}.threeSum(nums);
        System.out.println(lists);

    }
}
